import demo2.BinaryTree;

//class Solution {
//
//    public int preIndex = 0;
//    public TreeNode buildTreeChild(int[] preorder, int[] inorder, int ib, int ie){
//        if(ie<ib){
//            return null;
//        }
//      TreeNode root = new TreeNode(preorder[preIndex]);
//        //在中序数组中查找这个根节点来确定根
//        int rootIndex = findRootNode(preorder,inorder,ib,ie);
//        preIndex++;//创建下一个根节点
//        root.left = buildTreeChild(preorder,inorder,ib,rootIndex-1);//创建左子树
//        root.right = buildTreeChild(preorder,inorder,rootIndex+1,ie);//创建右子树
//        return root;
//    }
//
//    public int findRootNode(int[] preorder, int[] inorder,int ib,int ie){
//        for(int i = ib;i<=ie;++i){
//            if(preorder[preIndex]==inorder[i]){
//                return i;
//            }
//        }
//        return -1;
//    }
//
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        //先序确定根
//        return buildTreeChild(preorder,inorder,0,inorder.length-1);
//    }
//    public static void main(String[] args) {
//
//        Solution solution = new Solution();
//        //inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
//        int[] preorder = {3,9,20,15,7};
//        int[] inorder = {9,3,15,20,7};
//        solution.buildTree(preorder,inorder);
//        Solution solution = new Solution();
//        //inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
//        int[] inorder = {9,3,15,20,7};
//        int[] postorder = {9,15,7,20,3};
//        solution.buildTree(inorder,postorder);
//    }
//}


class Solution {
    public int preIndex = 0;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int ib,int ie){
        if(ie<ib){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        //在中序数组中查找这个根节点来确定根
        int rootIndex = findRootNode(preorder,inorder,ib,ie);
        preIndex++;//创建下一个根节点
        root.left = buildTreeChild(preorder,inorder,ib,rootIndex-1);//创建左子树
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,ie);//创建右子树
        return root;
    }

    public int findRootNode(int[] preorder, int[] inorder,int ib,int ie){
        for(int i = ib;i<=ie;++i){
            if(preorder[preIndex]==inorder[i]){
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //先序确定根
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        //inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
        int[] inorder = {9,3,15,20,7};
        int[] postorder = {9,15,7,20,3};
        solution.buildTree(inorder,postorder);
    }
}


